/*
 * @lc app=leetcode.cn id=34 lang=golang
 * @lcpr version=30118
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
func searchRange(nums []int, target int) []int {
	leftIdx, rightIdx := -1, -1

	l, r := 0, len(nums)-1

	// 找到第一个等于target的
	for l <= r {
		mid := (l + r) / 2
		if nums[mid] < target {
			l = mid + 1
		} else if nums[mid] == target {
			leftIdx = mid
			r = mid - 1
		} else {
			r = mid - 1
		}
	}

	if leftIdx == -1 {
		return []int{-1, -1}
	}

	l, r = leftIdx, len(nums)-1
	for l <= r {
		mid := (l + r) / 2
		if nums[mid] < target {
			l = mid + 1
		} else if nums[mid] == target {
			rightIdx = mid
			l = mid + 1
		} else {
			r = mid - 1
		}
	}

	return []int{leftIdx, rightIdx}
}

// @lc code=end

/*
// @lcpr case=start
// [5,7,7,8,8,10]\n8\n
// @lcpr case=end

// @lcpr case=start
// [5,7,7,8,8,10]\n6\n
// @lcpr case=end

// @lcpr case=start
// []\n0\n
// @lcpr case=end

*/

